package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

//定义了函数类型Hash，采取依赖注入的方式，允许用于替换成自定义的Hash函数，也方便测试时替换，默认为crc32.ChecksumIEEE算法
type Hash func(data []byte)uint32

//Map是一致性哈希算法的主数据结构，包含4个成员变量：Hash函数hash，虚拟节点倍数replicas
//哈希环keys，虚拟节点与真实节点的映射表hashMap，键是虚拟节点的哈希值，值是真实节点的名称
type Map struct {
	hash Hash
	replicas int
	keys []int
	hashMap map[int]string
}

//构造函数New()允许自定义虚拟节点背书和hash函数
func New(replicas int,fn Hash)*Map{
	m:=&Map{
		hash:     fn,
		replicas: replicas,
		hashMap:  make(map[int]string),
	}
	if m.hash==nil{
		m.hash=crc32.ChecksumIEEE
	}
	return m
}




//接下来，实现添加真实节点/机器的Add()方法
//Add函数允许传入0或多个真实节点的名称
//对每一个真实节点key，对应创建m.replicas个虚拟节点，虚拟节点的名称是：strconv.Itoa(i)+key
//即通过添加编号的方式区分不同的虚拟节点
//使用m.hash()计算虚拟节点的哈希值，使用append(m.keys,hash)添加到环上
//在hashMap中增加虚拟节点和真实节点的映射关系
//最后一步，环上的哈希值排序
func (m *Map)Add(keys ...string){//添加每个真实节点的名称
	for _,key:=range keys{//这是真实节点的名称
		for  i:=0;i<m.replicas;i++{//为每个真实节点创建虚拟节点
			hash:=int(m.hash([]byte(strconv.Itoa(i)+key)))
			m.keys=append(m.keys,hash)
			m.hashMap[hash]=key//对应的节点的名称,即每个虚拟节点对应的节点名称
		}
	}
	sort.Ints(m.keys)
}

//最后一步，实现选择节点的Get()方法
//选择节点就非常简单了，第一步，计算key的哈希值
//第二步，顺时针找到第一个匹配的虚拟节点的下标idx，从m.keys中获取到对应的哈希值，如果idx==len(m.keys)说明选择m.keys[0]，因为m.keys是一个环状结构，所以用取余数的方式来处理这种情况。
//第三步，通过hashMap映射得到真实的节点
func (m *Map)Get(key string)string{//根据key找到对应的真实节点
	if len(m.keys)==0{//根据key找到对应的节点
		return ""
	}
	hash:=int(m.hash([]byte(key)))
	idx:=sort.Search(len(m.keys), func(i int) bool {
		return m.keys[i]>=hash
	})
	return m.hashMap[m.keys[idx%len(m.keys)]]//返回真正的真实节点
}
